__author__ = 'Administrator'


def bubbleSort(data):
    lens = len(data)
    if lens < 2: return data
    for i in range(0, lens - 1):
        m = i
        for j in range(i + 1, lens):
            if data[m] > data[j]:
                m = j
        if m != i:
            data[i], data[m] = data[m], data[i]
    return data


def insertSort(data):
    lens = len(data)
    if lens < 2:
        return data
    for i in range(1, lens):
        key = data[i]
        j = i - 1
        while j >= 0 and key < data[j]:
            data[j + 1] = data[j]
            j = j - 1
        data[j + 1] = key
    return data


def mergeSort(data):
    lens = len(data)
    if lens < 2: return data
    left = data[:lens // 2]
    right = data[lens // 2:]
    return merge(mergeSort(left), mergeSort(right))


def merge(left, right):
    data = []
    while len(left) > 0 and len(right) > 0:
        if left[0] < right[0]:
            data.append(left.pop(0))
        else:
            data.append(right.pop(0))
    if len(left) > 0:
        data.extend(left)
    else:
        data.extend(right)
    return data


def heapSort(data):
    output = []
    buildHeap(data)
    while data:
        i = len(data) - 1
        data[0], data[i] = data[i], data[0]
        output.append(data.pop())
        if data:
            minHeapify(data, 0)
    return output


def minHeapify(data, i):
    if i < 0:
        return
    left = 2 * i + 1
    right = 2 * i + 2
    smallest = i
    length = len(data)
    if left < length:
        if data[i] > data[left]:
            smallest = left
        if right < length:
            if data[smallest] > data[right]:
                smallest = right
        if smallest != i:
            data[i], data[smallest] = data[smallest], data[i]
            minHeapify(data, smallest)


def buildHeap(data):
    length = len(data)
    if length < 2:
        return
    nonLeaf = length // 2
    for i in range(nonLeaf, -1, -1):
        minHeapify(data, i)


def test(fn):
    import random

    if fn is None: return
    data = [random.randint(0, 100) for i in range(10)]
    print(data)
    print('----%s----' % fn.__name__)
    print(fn(data[:]))
    print('=================================================')


def startTest():
    try:
        for i in [bubbleSort, insertSort, mergeSort, heapSort]:
            if i is not None: test(i)
    except Exception as e:
        pass


startTest()
